home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 2.iso / BARNET / COMPILER / SATHER / !Sather / Library / Graphs / sa / digrph_inc < prev    next >
Text File  |  1996-07-13  |  4KB  |  116 lines
  1. ---------------------------> Sather 1.1 source file <--------------------------
  2. -- Author: Benedict A. Gomes <gomes@tiramisu.ICSI.Berkeley.EDU>
  3. -- Copyright (C) 1995, International Computer Science Institute
  4. -- COPYRIGHT NOTICE: This code is provided WITHOUT ANY WARRANTY
  5. -- and is subject to the terms of the SATHER LIBRARY GENERAL PUBLIC
  6. -- LICENSE contained in the file: Sather/Doc/License of the
  7. -- Sather distribution. The license is also available from ICSI,
  8. -- 1947 Center St., Suite 600, Berkeley CA 94704, USA.
  9. -------------------------------------------------------------------
  10. partial class RO_DIGRAPH_INCL{NTP} < $RO_DIGRAPH{NTP} is
  11.    -- Partial class used to define other routines in digraphs
  12.    -- Usage:
  13.    --     g: DIGRAPH{INT} := #;
  14.    --     g.add_node(1).add_node(2).add_node(3).connect(1,2).connect(1,3);
  15.    --     Constructs:
  16.    --      1
  17.    --      /\
  18.    --     2  3
  19.    --
  20.    --    Getting the nodes in depth first order:
  21.    --       l:LIST{INT} := #;
  22.    --       loop n: INT := DAG_ALG{INT, DIGRAPH{INT}}::dfs!(g);
  23.    --           l := l.append(n);
  24.    --        end;
  25.  
  26.    --           --------- CORE FEATURES (must define) ---------
  27.    stub has_node(n: NTP): BOOL;
  28.    stub has_edge(e: DIEDGE{NTP}): BOOL; 
  29.    stub n_nodes: INT; 
  30.    stub n_edges: INT;
  31.    stub n_incoming(n: NTP): INT;
  32.    stub n_outgoing(n: NTP): INT; 
  33.    stub node!: NTP; 
  34.    stub edge!: DIEDGE{NTP}; 
  35.    stub incoming!(once n: NTP): NTP; 
  36.    stub outgoing!(once n: NTP): NTP; 
  37.  
  38.    --              ------ Initialization/Duplication ------
  39.    copy: $DIGRAPH{NTP} is
  40.       res ::= #DIGRAPH{NTP};
  41.       loop res.add_node(node!) end;
  42.       loop res.connect(edge!) end;
  43.       return res;
  44.    end;
  45.    
  46.    --              ------ Queries/Comparison --------------
  47.    size: INT is return n_nodes end;
  48.  
  49.    has(n: NTP): BOOL is return has_node(n) end;
  50.    
  51.    is_empty: BOOL is return n_nodes = 0 end;
  52.    
  53.    n_adjacent(n:NTP): INT is return n_outgoing(n) end;
  54.    
  55.    equals(g: $RO_DIGRAPH{NTP}):BOOL is
  56.       -- True if both have the same set of nodes and edges
  57.       if g.n_nodes /= n_nodes then return false end;
  58.       if g.n_edges /= n_edges then return false end;
  59.       loop n ::= node!; if ~g.has_node(n) then return false end; end;
  60.       loop e ::= edge!; if ~g.has_edge(e) then return false end; end;
  61.       return true;
  62.    end;
  63.  
  64.    --              ------ Cursor --------------------------
  65.    elt!: NTP is loop yield node! end; end;
  66.    -- Returns the nodes of the graph
  67.    
  68.    adjacent!(once n: NTP): NTP is loop yield outgoing!(n) end; end;
  69.    -- Adjacent is aliased to "outgoing"
  70.    
  71.    --              ------ Conversion ----------------------
  72.    str: STR is
  73.       -- Print out the graph using the bound routine "f"
  74.       -- for the nodes   
  75.       res ::= #FSTR("");
  76.       loop n ::= node!;
  77.      -- if void(n) then res := res + "void  : ";
  78.      -- Should never have "void" nodes in the graph.
  79.      -- If they are value types, then void might be 0 or something useful
  80.      res := res + "["+node_str(n)+"] "; 
  81.      res := res + "<-";
  82.      loop res := res + ",".separate!(node_str(incoming!(n))); end;
  83.      res := res + "  ->";
  84.      loop res := res + ",".separate!(node_str(outgoing!(n))); end;
  85.      res := res+"\n";        -- End of another row of edges
  86.       end; -- All graph nodes
  87.       return(res.str);
  88.    end;   
  89.  
  90.    private node_str(n: NTP): STR is
  91.       -- There should not be void nodes in the graph!
  92.       typecase n
  93.       when $STR then  return(n.str); 
  94.       else return("") end;
  95.    end;
  96.    
  97. end;
  98. -------------------------------------------------------------------
  99. partial class DIGRAPH_INCL{NTP} < $DIGRAPH{NTP} is
  100.    include RO_DIGRAPH_INCL{NTP};
  101.  
  102.    --           --------- CORE FEATURES (must define) ---------
  103.    stub add_node: NTP;
  104.    stub add_node(n: NTP): NTP;
  105.    stub connect(e: DIEDGE{NTP});
  106.    stub delete_node(n: NTP);
  107.    stub disconnect(e: DIEDGE{NTP});
  108.    
  109.    -- Auxilliary versions of core features
  110.    connect(f,s: NTP) is connect(#DIEDGE{NTP}(f,s)) end;   
  111.    disconnect(f,s: NTP) is disconnect(#DIEDGE{NTP}(f,s)) end;   
  112.    connect(f,s: NTP): SAME is connect(f,s); return self end;
  113.       
  114. end; -- class DIGRAPH_INCL
  115. -------------------------------------------------------------------
  116.